package Ep06_BinaryTree.BT32_0108;


import Ep06_BinaryTree.TreeNode;

/**
 * @author Jimmy Zhan WORKSTATION
 * @date 2023/7/9 18:14
 * 说明：108. 将有序数组转换为二叉搜索树
 *      要求是一棵平衡BST，否则任何一个数组都可以用一条链表来表示，那就没有意义了
 *      因此我们取数组的中间节点作为root，每次递归也取中间节点作为子树的root，这样就能保证平衡
 */

public class Mine {
    public TreeNode sortedArrayToBST(int[] nums) {
        return traversal(nums, 0, nums.length-1);
    }

    private TreeNode traversal(int[] nums, int left, int right) {
        if (left > right) return null;
        int mid = (left + right) / 2;
        // 创建当前节点
        TreeNode root = new TreeNode(nums[mid]);
        // 接收下面递归传上来的左右孩子
        root.left = traversal(nums, left, mid-1);
        root.right = traversal(nums, mid+1, right);
        return root;
    }
}
